package hot100;


/*
 * Author：江松
 * Date：2023/4/11 16:30
 *
 找到所有数组中消失的数字：
 1，哈希表
 2,空间O(1)时间O(n)
 让原数组充当哈希表
 首先，num+n，这样就能保证出现的值>n
 第一步改变了原数组，可以用取模运算还原
 */

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class Main448 {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n=nums.length;
        List<Integer>res=new LinkedList<>();
        for(int i=0;i<n;++i){
            //下标0-n-1
            nums[(nums[i]-1)%n]+=n;
        }
        for(int i=0;i<n;++i){
            if(nums[i]<=n){
                res.add(i+1);
            }
        }
        return res;
    }
    /*
    public List<Integer> findDisappearedNumbers(int[] nums) {
        HashMap<Integer,Integer>map=new HashMap<>();
        List<Integer>res=new LinkedList<>();
        for(int i:nums){
            map.put(i,map.getOrDefault(i,0)+1);
        }
        for(int i=1;i<=nums.length;++i){
            if(map.get(i)==null){
                res.add(i);
            }
        }
        return res;
    }
    */
}
